package org.usmile.algorithms.leetcode.middle;

import java.util.ArrayList;
import java.util.List;

/**
 * 842. 将数组拆分成斐波那契序列
 *
 * 给定一个数字字符串 num，比如 "123456579"，我们可以将它分成「斐波那契式」的序列 [123, 456, 579]。
 * 形式上，斐波那契式 序列是一个非负整数列表 f，且满足：
 * 0 <= f[i] < 231 ，（也就是说，每个整数都符合 32 位 有符号整数类型）
 * f.length >= 3
 * 对于所有的0 <= i < f.length - 2，都有 f[i] + f[i + 1] = f[i + 2]
 * 另外，请注意，将字符串拆分成小块时，每个块的数字一定不要以零开头，除非这个块是数字 0 本身。
 * 返回从 num 拆分出来的任意一组斐波那契式的序列块，如果不能拆分则返回 []。
 *
 * 示例 1：
 * 输入：num = "1101111"
 * 输出：[11,0,11,11]
 * 解释：输出[110,1,111]也可以。
 *
 * 示例 2：
 * 输入: num = "112358130"
 * 输出: []
 * 解释: 无法拆分。
 *
 * 示例 3：
 * 输入："0123"
 * 输出：[]
 * 解释：每个块的数字不能以零开头，因此 "01"，"2"，"3" 不是有效答案。
 *
 * 提示：
 * 1 <= num.length <= 200
 * num 中只含有数字
 */
public class _0842 {
}

class _0842_Solution {
    private String num;
    private List<Integer> res;

    public List<Integer> splitIntoFibonacci(String num) {
        this.num = num;
        this.res = new ArrayList<>();
        dfs(0, 0, 0);
        return res;
    }

    private boolean dfs(int startIndex, int prevTwoNumSum, int prevNum) {
        if (startIndex == num.length()) {
            return res.size() >= 3;
        }

        long currLongNum = 0;
        for (int i = startIndex; i < num.length(); i++) {
            // 如果当前字符是 '0' 的话，则不做处理，因为数字不能以 0 开头
            if (i > startIndex && num.charAt(startIndex) == '0') {
                continue;
            }

            currLongNum = currLongNum * 10 + (num.charAt(i) - '0');
            if (currLongNum > Integer.MAX_VALUE) {
                break;
            }
            int currNum = (int) currLongNum;

            if (res.size() >= 2) {
                if (currNum < prevTwoNumSum) {
                    continue;
                } else if (currNum > prevTwoNumSum) {
                    break;
                }
            }

            res.add(currNum);
            if (dfs(i + 1, currNum + prevNum, currNum)) {
                return true;
            }
            res.remove(res.size() - 1);
        }

        return false;
    }
}
